Field of the Invention: The present invention relates generally to the field of knowledge based systems; that is, computer systems that emulate reasoning tasks by using a so-called "inference engine" to interpret encoded knowledge of human experts stored in a "knowledge base". If the domain of the knowledge base, or scope of the problem, is sufficiently narrow and a sufficiently large body of the knowledge is properly coded in the knowledge base, then the knowledge based system can achieve performance that matches or exceeds the ability of a human expert. In such a case, the knowledge based system is called an "expert system."
More specifically, the present invention relates to a method of converting both a knowledge base and an "inference engine" into program source code which may be compiled into object code for execution by a computer, thereby increasing the execution speed of the expert system.
Introduction: While knowledge based system technologies have shown promise in many useful applications, their use in some areas has been impaired by the limited performance of the presently known implementations. This is particularly true in real-time monitoring and control applications which must reason large amounts of data in a very short period of time and in embedded applications in which the knowledge based system must share the resources of the computer with a number of other applications.
While the performance of current knowledge based systems may be improved through the development of special hardware to support the reasoning process, a major performance limitation for knowledge based systems on conventional hardware is due to the inherent interpretive nature of their implementations. Even when an "inference engine" is implemented in a compiled language, the general purpose design the inference engine requires the interpretation of data structures representing the knowledge base. This process of interpretation is inefficient in comparison to compiled implementations. Compilation of the knowledge bases can be performed by restricting the inferencing techniques available to decision trees or other single paradigm reasoning strategies; however, this restriction limits the knowledge engineer's ability to represent and solve some classes of problems.
Interpretive Implementations of Reasoning: Most knowledge based systems represent knowledge internally as collections of data structures. The data structures are composed of nodes and links between the nodes. The nodes represent the rules and the tests within the rules. Included in the nodes are: how facts are tested and the results of these tests, how to acquire the facts, the operations performed on the facts and the means of processing the results of the tests. The links represent the way in which facts and the results of tests are combined into rule conditions, the references made to these tests and rule conditions by other rules in the knowledge base, and the actions to be performed when a rule is "true". The nodes are usually organized into trees or networks which are augmented with lists of references or current data values. These networks are traversed by the inference engine to implement the reasoning process. At each node, the inference engine must examine the contents of the node to determine what data is involved and what tests need to be performed on that data (test evaluation), which nodes to process next based on the results of these tests (test result propagation), and what actions to perform when a rule becomes true (performance of rule actions). Based on the results of this process the inference engine must then follow one or more links to the other nodes. This is the essence of the interpretive process.
As an example of this, consider a simple backward chaining system which organizes its rules as a set of goal trees, each containing one or more rules that provide conditions and fact values concluding in a single goal. A particular set of such rules, and a goal tree that would result from them, is represented in FIG. 1. The reasoning process for such a system would begin by selecting a goal and then "depth-first" traversing the respective goal tree to locate a fact that is not currently known. The value for the fact is then acquired by interpreting information in the fact node that indicates how to obtain the value. Next, test evaluation occurs by interpreting information in the test nodes that reference that fact. The results of these tests are then propagated up the goal tree by reversing the traversal process and interpreting each node to determine how the results of previous nodes are to be combined and passed to the next node in the tree. In addition to the interpretation that must be performed for test evaluation and result propagation, the tree traversal process must also be interpretive because connections are only known to the nodes which represent the trees. This form of backward chaining reasoning mechanism is similar to that of EMYCIN (Van Melle et al, "The EMYCIN Manual", Heuristic Programming Project Report HPP-81-16, Stanford University, 1981); PIE (Burns et al., "The Portable Inference Engine: Fitting Significant Expertise into Small Systems", IBM Systems Journal, Vol. 25, No. 2, 1986), and example systems proposed by Winston and Horn (LISP, 2nd Ed., Chapter 18, "Expert Problem Solving using Rules and Streams," Addison Wesley, Reading, Mass., 1984).
Other known knowledge based systems are disclosed in the U.S. Pat. Nos. 4,591,983; 4,648,044 and 4,713,775, all assigned to Teknowledge Inc., Palo Alto. Calif.
Forward chaining reasoning algorithms differ from backward chaining in that they work forward from facts to goals. The tree or network form of knowledge representation may still be used but the depth-first traversal to find a fact to evaluate is not performed. Instead, the system must search for facts that match rule conditions. Typically, this involves propagation of data values to the rules that use that data and evaluation of rule tests based on that data. This again involves interpretation of the test nodes to evaluate these tests with respect to a set of facts. After a test is evaluated, the results are propagated up the goal trees by interpreting the nodes at each step to determine how the results of previous nodes are to be processed, combined and passed to the next node in the network. This form of forward chaining reasoning mechanism is similar to that of example systems proposed by Winston and Horn (LISP. 2nd Ed., Chapter 18, Addison Wesley, Reading, Mass., 1984) and has been highly optimized in OPS5 (Forgy, "Rete: A Fast Algorithm for the Many Pattern/Many Object Match Problem", Artificial Intelligence, Vol. 19, 1982).
The interpretive traversal of these trees or networks and the determination of the steps required to process each node degrades the performance of the reasoning process. At each node, the reasoning system must determine which of a possible set of steps are required and then perform those steps using information available at the node. Once the steps required to process a node have been performed, a determination of which node(s) to process next must be made. The performance of knowledge based systems could be greatly improved if the interpretation process were eliminated and the equivalent steps were performed by concise, compiled program code.